ON A FINITE BASIS SET FOR SUPERPOSITION IN THE CLASS OF FUNCTIONS COMPUTABLE ON NONDESTRUCTIVE TURING MACHINES WITH OUTPUT

Osipov Kirill Vladimirovich, Postgraduate student, Lomonosov Moscow State University (1 Leninskie Gory street, Moscow, Russia), d503@acmer.me

519.716

10.21685/2072-3040-2016-3-5

Background. More than 60 years ago A. Grzegorczyk couched the problem of existence of finite basis sets for superposition in classes of recursive functions,which create a hierarchy of the set of all primitive recursive functions. This problem was resolved by various authors for many large and meaningful interesting classes of recursive functions. Resulting from an increased interest to the study of polynomial- time computable functions over the last years, this issue again has been considered for relatively small classes of such functions. In particular, classes of functions that are polynomial-time computable for different variants of Turing machines, which comply with strong restrictions on the structure and methods of operation with external memory, are of great interest right now. The solution of the problem of existence of a finite basis set for superposition in such classes of functions would allow us to understand the nature of polynomial computation deeper and may adduce additional arguments to the solution of the problem of a ratio of deterministic and nonedeterministic polynomial calculations. The aim of this work is to build a finite basis set for superposition in the C-class of functions, (polynomial-time) computable at nondestructive Turing machines with output. The C-class has been recently introduced by S. S. Marchenkov for obtaining the "upper boundary" of the complexity of computing functions, obtained by a limited prefix of the concatenation, and has not been explicitly studied.
Materials and methods. There was employed the method of proving the existence of a finite basis for superposition, based on the use of a quasi-universal function.
Results and conclusions. The author built quasi-universal functions for the C-class of functions computable at nondestructive Turing machines with output. The resulting function is used to obtain a finite basis for superposition in the C-class. This result can be applied to solve similar problems in classes of computable functions that are close to the C-class.

nondestructive Turing machines with output, polynomial calculations, finite basis set for superposition.

1. Grzegorczyk A. Rozprawy Matematyczne [Mathematical apparatus]. 1953, vol. 4, pp. 1–46.
2. Rödding D. Z. Math. Logik Grundlagen Math. [Foundations of mathematical logic].1964,vol.10,pp.315–330.
3. Marchenkov S. S. Matematicheskie zametki [Mathematical notes]. 1969, vol. 5, no. 5, pp. 561–568.
4. Volkov S. A. Diskretnaya matematika [Discrete mathematics]. 2006, vol. 18, no. 4, pp. 31–44.
5. Mazzanti S. Mathematical Logic Quarterly. 2002, vol. 48, pp. 93–104.
6. Marchenkov S. S. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 1991, iss. 3, pp. 115–139.
7. Osipov K. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2016, no. 1, pp. 28–34.
8. Marchenkov S. S. Diskretnaya matematika [Discrete mathematics]. 2015, vol. 27, no. 3, pp. 44–55.